package listbyorder.access101_200.test130;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/10 9:37
 */
public class Solution3 {

    // 方法三： 并查集结构
    int rows, cols;

    public void solve(char[][] board) {
        if (board == null || board.length == 0) return;

        rows = board.length;
        cols = board[0].length;

        //多申请一个空间
        UnionFind uf = new UnionFind(rows * cols + 1);
        //所有边界的 O 节点都和 dummy 节点合并
        int dummyNode = rows * cols;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (board[i][j] == 'O') {
                    //当前节点在边界就和 dummy 合并
                    if (i == 0 || i == rows - 1 || j == 0 || j == cols - 1) {
                        uf.union(dummyNode, node(i, j));
                    } else {
                        //将上下左右的 O 节点和当前节点合并
                        if (board[i - 1][j] == 'O') uf.union(node(i, j), node(i - 1, j));
                        if (board[i + 1][j] == 'O') uf.union(node(i, j), node(i + 1, j));
                        if (board[i][j - 1] == 'O') uf.union(node(i, j), node(i, j - 1));
                        if (board[i][j + 1] == 'O') uf.union(node(i, j), node(i, j + 1));
                    }
                }
            }
        }

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                //判断是否和 dummy 节点是一类
                if (uf.isConnected(node(i, j), dummyNode)) {
                    board[i][j] = 'O';
                } else {
                    board[i][j] = 'X';
                }
            }
        }
    }

    int node(int i, int j) {
        return i * cols + j;
    }

    // 创建并查集结构
    class UnionFind {
        // 维护一个parents数据，元素索引表示当前元素在二维数组中的位置，值表示他属于哪一个类
        int[] parents;

        public UnionFind(int totalNodes) {
            parents = new int[totalNodes];
            // 初始化，让每一个节点自成一类
            for (int i = 0; i < totalNodes; i++) {
                parents[i] = i;
            }
        }

        // 合并两个节点
        void union(int node1, int node2) {
            int root1 = find(node1);
            int root2 = find(node2);
            // 入过两个节点所在的集合不一样，则将root2的父节点设置成为root1
            if (root1 != root2) {
                parents[root2] = root1;
            }
        }

        // 寻找当前节点所在的集合
        int find(int node) {
            while (parents[node] != node) {
                parents[node] = parents[parents[node]];
                node = parents[node];
            }
            return node;
        }

        // 检查两个节点是否在同一个集合中
        boolean isConnected(int node1, int node2) {
            return find(node1) == find(node2);
        }
    }
}
